package leetcode_二分查找;

/**
 * 寻找两个正序数组的中位数
 * 算法: 二分查找
 * 将寻找两个数组的中位数转化成寻找两个数组的第 k 小的数
 * 每次取两个数组的前 k / 2 个数, 如果 nums1[s1 + k / 2 - 1] < nums2[s2 + k / 2 - 1], 则说明
 * 第 k 小的数肯定不在 nums1 的 [s1, s1 + k / 2 - 1] 中, 直接将这个区间排除
 * 依次类推
 *
 * @author yezh
 * @date 2023/3/26 14:16
 * @see <a>https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/</a>
 */
public class _04 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        return (findKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + findKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    int findKth(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, int k) {
        int len1 = e1 - s1 + 1, len2 = e2 - s2 + 1;
        // 保证如果有数组空了, 一定是 nums1
        if (len1 > len2) return findKth(nums2, s2, e2, nums1, s1, e1, k);
        if (len1 == 0) return nums2[s2 + k - 1];
        if (k == 1) return Math.min(nums1[s1], nums2[s2]);
        int i = s1 + Math.min(len1, k / 2) - 1;
        int j = s2 + Math.min(len2, k / 2) - 1;
        if (nums1[i] < nums2[j]) return findKth(nums1, i + 1, e1, nums2, s2, e2, k - (i + 1 - s1));
        else return findKth(nums1, s1, e1, nums2, j + 1, e2, k - (j + 1 - s2));
    }

}
